#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct elem {
    char *data;          
    struct elem *next;   
};

struct elem *create_elem() {
    char data[30];                    
    scanf("%s", data);              
    
    struct elem *element = (struct elem *)malloc(sizeof(struct elem));
    if (element == NULL) {         
        printf("element malloc failed\n");
        return element;
    }

    int data_len = strlen(data);     
    element->data = (char *)malloc((data_len + 1) * sizeof(char)); 
    if (element->data == NULL) {     
        printf("element->data malloc failed\n");
        free(element);                
        element = NULL;
        return element;
    }

    strcpy(element->data, data);      
    element->next = NULL;             
    return element;
}


void print_elem(struct elem *element) {
    printf("data: %s; next: %p\n", element->data, element->next); 
}


struct list {
    struct elem *head, *tail; 
    int length;              
};


struct list *create_list() {
    struct list *lst = (struct list *)malloc(sizeof(struct list)); 
    lst->head = NULL;
    lst->tail = NULL;

    struct elem *head_elem = create_elem();
    lst->head = head_elem;                  
    lst->tail = lst->head;                 
    lst->length = 1;                       
    return lst;
}


void print_list(struct list *lst) {
    struct elem *element = lst->head;
    printf("list->length: %d\n", lst->length);
    for (int i = 0; i < lst->length; i++) { 
        print_elem(element);                
        element = element->next;
    }
}

struct list *append_list_tail(struct list *lst) {
    if (lst == NULL) {                      
        return create_list();
    } else if (lst->head == NULL) {         
        free(lst);
        lst = NULL;
        return create_list();
    } else {
        struct elem *element = create_elem(); 
        lst->tail->next = element;            
        lst->tail = element;                  
        lst->length += 1;                    
        return lst;
    }
}


struct list *append_list_head(struct list *lst) {
    if (lst == NULL) {
        return create_list();
    } else if (lst->head == NULL) {
        free(lst);
        lst = NULL;
        return create_list();
    } else {
        struct elem *element = create_elem(); 
        element->next = lst->head;            
        lst->head = element;                  
        lst->length += 1;                     
        return lst;
    }
}


struct list *insert_list(struct list *lst, int index) {
    if (index == 0) {
        return append_list_head(lst);
    } else if (index == lst->length) {
        return append_list_tail(lst);
    } else if (index < 0 || index > lst->length) {
        printf("Index is out of range\n");
        return lst;
    } else {
        struct elem *element = create_elem(); 
        struct elem *current_node = lst->head;
        for (int i = 0; i < index - 1; i++) { 
            current_node = current_node->next;
        }
        element->next = current_node->next;   
        current_node->next = element;         
        lst->length++;
        return lst;
    }
}

int search_value(struct list *lst, char *value) {
    if ((lst != NULL) && (lst->head != NULL)) {
        struct elem *current_node = lst->head;
        int index = 0;
        while (strcmp(current_node->data, value) != 0) { 
            if (current_node->next == NULL) {           
                printf("The value: %s is not in the list\n", value);
                return -2;
            }
            current_node = current_node->next;
            index++;
        }
        return index;
    } else {
        printf("Input list is not available\n");
        return -1;
    }
}


char *search_index(struct list *lst, int index) {
    if (lst == NULL || lst->head == NULL) {
        printf("List input is not available\n");
        return NULL;
    }
    if (index < 0 || index >= lst->length) {
        printf("The index: %d is out of range!\n", index);
        return NULL;
    }
    struct elem *current_node = lst->head;
    for (int i = 0; i < index; i++) {       
        current_node = current_node->next;
    }
    return current_node->data;
}

struct list *remove_head(struct list *lst) {
    if (lst == NULL || lst->head == NULL) {
        printf("List input is not available\n");
        return NULL;
    }
    struct elem *temp = lst->head;         
    lst->head = temp->next;                
    free(temp);                            
    lst->length--;
    return lst;
}


struct list *remove_tail(struct list *lst) {
    if (lst == NULL || lst->head == NULL) {
        printf("List input is not available\n");
        return NULL;
    }
    struct elem *current = lst->head;
    struct elem *prior = NULL;
    while (current->next != NULL) {         
        prior = current;
        current = current->next;
    }
    lst->tail = prior;                     
    free(current);                         
    lst->length--;
    return lst;
}


struct list *remove_index(struct list *lst, int index) {
    if (lst == NULL || lst->head == NULL || index < 0 || index >= lst->length) {
        printf("Index %d is out of range\n", index);
        return NULL;
    }
    if (index == 0) {
        return remove_head(lst);
    } else if (index == lst->length - 1) {
        return remove_tail(lst);
    } else {
        struct elem *current_node = lst->head;
        for (int i = 0; i < index - 1; i++) { 
            current_node = current_node->next;
        }
        struct elem *temp = current_node->next; 
        current_node->next = temp->next;        
        free(temp);                             
        lst->length--;
        return lst;
    }
}


int delete_list(struct list *lst) {
    if (lst == NULL) {
        printf("List is NULL\n");
        return -1;
    } else if (lst->head == NULL) {
        free(lst);
        printf("List->head is NULL\n");
        return -2;
    } else {
        struct elem *current_element;
        while (lst->head != lst->tail) {    
            current_element = lst->head;
            lst->head = lst->head->next;
            free(current_element);
        }
        free(lst->head);                  
        free(lst);                          
        return 0;
    }
}

int main() {
    struct list *lst = create_list();       
    for (int i = 0; i < 4; i++)             
        lst = append_list_tail(lst);
    print_list(lst);                        
    lst = remove_index(lst, 3);             
    print_list(lst);                        
    delete_list(lst);                       
    return 0;
}
